SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Randomness extractor</title>

</head>

Randomness extractor

</h1>

</header>

A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak <a href="Entropy_source" class="mw-redirect" title="Entropy source">entropy source</a>, together with a short, uniformly random seed, generates a highly <a href="Random" class="mw-redirect" title="Random">random</a> output that appears <a href="Independent_and_identically_distributed_random_variables" title="Independent and identically distributed random variables">independent</a> from the source and <a href="Uniform_distribution_(discrete)" class="mw-redirect" title="Uniform distribution (discrete)">uniformly distributed</a>.<a href="#cite_note-1">[1]</a> Examples of weakly random sources include <a href="Radioactive_decay" title="Radioactive decay">radioactive decay</a> or <a href="Thermal_noise" class="mw-redirect" title="Thermal noise">thermal noise</a>; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (<a href="Hardware_random_number_generator" title="Hardware random number generator">TRNG</a>); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source.

Sometimes the term "bias" is used to denote a weakly random source's departure from uniformity, and in older literature, some extractors are called unbiasing algorithms,<a href="#cite_note-2">[2]</a> as they take the randomness from a so-called "biased" source and output a distribution that appears unbiased. The weakly random source will always be longer than the extractor's output, but an efficient extractor is one that lowers this ratio of lengths as much as possible, while simultaneously keeping the seed length low. Intuitively, this means that as much randomness as possible has been "extracted" from the source.

An extractor has some conceptual similarities with a <a href="Pseudorandom_generator" title="Pseudorandom generator">pseudorandom generator</a> (PRG), but the two concepts are not identical. Both are functions that take as input a small, uniformly random seed and produce a longer output that "looks" uniformly random. Some pseudorandom generators are, in fact, also extractors. (When a PRG is based on the existence of <a href="Hard-core_predicate" title="Hard-core predicate">hard-core predicates</a>, one can think of the weakly random source as a set of truth tables of such predicates and prove that the output is statistically close to uniform.<a href="#cite_note-3">[3]</a>) However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be <a href="Statistically_close" class="mw-redirect" title="Statistically close">statistically close</a> to uniform, in a PRG it is only required to be <a href="Computationally_indistinguishable" class="mw-redirect" title="Computationally indistinguishable">computationally indistinguishable</a> from uniform, a somewhat weaker concept.

<div class="mw-heading mw-heading2"><h2 id="Formal_definition_of_extractors">Formal definition of extractors</h2></div>

The <a href="Min-entropy" title="Min-entropy">min-entropy</a> of a distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> (denoted <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{\infty }(X)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{\infty }(X)}</annotation>

</semantics>

</math><img src="./8f9d07787f0576e11a938a0c1639763dc84a81d8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.596ex; height:2.843ex;" alt="{\displaystyle H_{\infty }(X)}" loading="lazy">), is the largest real number <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> such that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr[X=x]\leq 2^{-k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pr[X=x]\leq 2^{-k}}</annotation>

</semantics>

</math><img src="./e5c83b8ba7cac6c82bbe05a687a2e8dc99e03a29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.824ex; height:3.176ex;" alt="{\displaystyle \Pr[X=x]\leq 2^{-k}}" loading="lazy"> for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> in the range of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">. In essence, this measures how likely <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is to take its most likely value, giving a worst-case bound on how random <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> appears. Letting <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\ell }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\ell }}</annotation>

</semantics>

</math><img src="./62bd10673cb3f4c7c2dabdace496a2f044a7e3c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.505ex; height:2.509ex;" alt="{\displaystyle U_{\ell }}" loading="lazy"> denote the uniform distribution over <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}^{\ell }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1\}^{\ell }}</annotation>

</semantics>

</math><img src="./40891b89c4cd332ac4fbd27f654d8573e4259293.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.602ex; height:3.176ex;" alt="{\displaystyle \{0,1\}^{\ell }}" loading="lazy">, clearly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{\infty }(U_{\ell })=\ell }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{\infty }(U_{\ell })=\ell }</annotation>

</semantics>

</math><img src="./029f4ffffbf62648cb47ee9dfe5669bd1df6ff5b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.189ex; height:2.843ex;" alt="{\displaystyle H_{\infty }(U_{\ell })=\ell }" loading="lazy">.

For an n-bit distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> with min-entropy k, we say that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> is an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)}</annotation>

</semantics>

</math><img src="./47f4659640cd0bb3ab77e4d61a81328ca4dd8a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.449ex; height:2.843ex;" alt="{\displaystyle (n,k)}" loading="lazy"> distribution.

Definition (Extractor): (k, ε)-extractor

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}</annotation>

</semantics>

</math><img src="./fe919574c900e789da0da2e6a1c0b9be8059c224.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.143ex; height:3.176ex;" alt="{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}" loading="lazy">

be a function that takes as input a sample from an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)}</annotation>

</semantics>

</math><img src="./47f4659640cd0bb3ab77e4d61a81328ca4dd8a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.449ex; height:2.843ex;" alt="{\displaystyle (n,k)}" loading="lazy"> distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> and a d-bit seed from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{d}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{d}}</annotation>

</semantics>

</math><img src="./a321d741a59ba8149c5d0077f222ef81ce44916c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.68ex; height:2.509ex;" alt="{\displaystyle U_{d}}" loading="lazy">, and outputs an m-bit string.

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Ext}}}</annotation>

</semantics>

</math><img src="./3fbe87fd94b9aa18833d92e77eacadf32dd17da4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.715ex; height:2.176ex;" alt="{\displaystyle {\text{Ext}}}" loading="lazy"> is a (k, ε)-extractor, if for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)}</annotation>

</semantics>

</math><img src="./47f4659640cd0bb3ab77e4d61a81328ca4dd8a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.449ex; height:2.843ex;" alt="{\displaystyle (n,k)}" loading="lazy"> distributions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">, the output distribution of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{Ext}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Ext}}}</annotation>

</semantics>

</math><img src="./3fbe87fd94b9aa18833d92e77eacadf32dd17da4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.715ex; height:2.176ex;" alt="{\displaystyle {\text{Ext}}}" loading="lazy"> is ε-close to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{m}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{m}}</annotation>

</semantics>

</math><img src="./b0c55bbcbf22a71ccbd6e116acfd21345f82262b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.263ex; height:2.509ex;" alt="{\displaystyle U_{m}}" loading="lazy">.

In the above definition, ε-close refers to <a href="Total_variation_distance" class="mw-redirect" title="Total variation distance">statistical distance</a>.

Intuitively, an extractor takes a weakly random n-bit input and a short, uniformly random seed and produces an m-bit output that looks uniformly random. The aim is to have a low <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> (i.e. to use as little uniform randomness as possible) and as high an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> as possible (i.e. to get out as many close-to-random bits of output as we can).

<div class="mw-heading mw-heading3"><h3 id="Strong_extractors">Strong extractors</h3></div>

An extractor is strong if <a href="Concatenation" title="Concatenation">concatenating</a> the seed with the extractor's output yields a distribution that is still close to uniform.

Definition (Strong Extractor): A <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (k,\epsilon )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (k,\epsilon )}</annotation>

</semantics>

</math><img src="./47f8a02fd64a74d14f7eaaef361708ddffa03a5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.999ex; height:2.843ex;" alt="{\displaystyle (k,\epsilon )}" loading="lazy">-strong extractor is a function

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,}</annotation>

</semantics>

</math><img src="./49fea27315ed3c6fdc05b20cd85ae0bff780f9c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.531ex; height:3.176ex;" alt="{\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,}" loading="lazy"></dd></dl>

such that for every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)}</annotation>

</semantics>

</math><img src="./47f4659640cd0bb3ab77e4d61a81328ca4dd8a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.449ex; height:2.843ex;" alt="{\displaystyle (n,k)}" loading="lazy"> distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> the distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{d}\circ {\text{Ext}}(X,U_{d})}">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{d}\circ {\text{Ext}}(X,U_{d})}</annotation>

</semantics>

</math><img src="./0517a6aef338ffbd0e8c5016ecf70d793a65cb76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.092ex; height:2.843ex;" alt="{\displaystyle U_{d}\circ {\text{Ext}}(X,U_{d})}" loading="lazy"> (the two copies of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{d}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{d}}</annotation>

</semantics>

</math><img src="./a321d741a59ba8149c5d0077f222ef81ce44916c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.68ex; height:2.509ex;" alt="{\displaystyle U_{d}}" loading="lazy"> denote the same random variable) is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy">-close to the uniform distribution on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{m+d}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{m+d}}</annotation>

</semantics>

</math><img src="./aefa5d57210bef442166ded8165ca8bbdaa1668b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.401ex; height:2.509ex;" alt="{\displaystyle U_{m+d}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="Explicit_extractors">Explicit extractors</h3></div>

Using the <a href="Probabilistic_method" title="Probabilistic method">probabilistic method</a>, it can be shown that there exists a (k, ε)-extractor, i.e. that the construction is possible. However, it is usually not enough merely to show that an extractor exists. An explicit construction is needed, which is given as follows:

Definition (Explicit Extractor): For functions k(n), ε(n), d(n), m(n) a family Ext = {Extn} of functions

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\rightarrow \{0,1\}^{m(n)}}</annotation>

</semantics>

</math><img src="./c37edde32dca3bcd943e1108b47590a82a85b265.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.893ex; height:3.343ex;" alt="{\displaystyle {\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\rightarrow \{0,1\}^{m(n)}}" loading="lazy"></dd></dl>

is an explicit (k, ε)-extractor, if Ext(x, y) can be computed in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> (in its input length) and for every n, Extn is a (k(n), ε(n))-extractor.

By the probabilistic method, it can be shown that there exists a (k, ε)-extractor with seed length

</mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=\log {(n-k)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)}</annotation>

</semantics>

</math><img src="./e52c1b60b371bfaa4e8937e437088b346cc72905.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:35.296ex; height:6.176ex;" alt="{\displaystyle d=\log {(n-k)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)}" loading="lazy"></dd></dl>

and output length

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)}</annotation>

</semantics>

</math><img src="./dc225ade022bfe451593c6e015788603ab9cb4c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:30.773ex; height:6.176ex;" alt="{\displaystyle m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)}" loading="lazy">.<a href="#cite_note-4">[4]</a></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Dispersers">Dispersers</h3></div>

A variant of the randomness extractor with weaker properties is the <a href="Disperser" title="Disperser">disperser</a>.

<div class="mw-heading mw-heading2"><h2 id="Randomness_extractors_in_cryptography">Randomness extractors in cryptography</h2></div>

One of the most important aspects of <a href="Cryptography" title="Cryptography">cryptography</a> is random <a href="Key_generation" title="Key generation">key generation</a>.<a href="#cite_note-5">[5]</a> It is often necessary to generate secret and random keys from sources that are semi-secret or which may be compromised to some degree. By taking a single, short (and secret) random key as a source, an extractor can be used to generate a longer pseudo-random key, which then can be used for public key encryption. More specifically, when a strong extractor is used its output will appear be uniformly random, even to someone who sees part (but not all) of the source. For example, if the source is known but the seed is not known (or vice versa). This property of extractors is particularly useful in what is commonly called Exposure-Resilient cryptography in which the desired extractor is used as an Exposure-Resilient Function (ERF). Exposure-Resilient cryptography takes into account that the fact that it is difficult to keep secret the initial exchange of data which often takes place during the initialization of an <a href="Encryption" title="Encryption">encryption</a> application e.g., the sender of encrypted information has to provide the receivers with information which is required for decryption.

The following paragraphs define and establish an important relationship between two kinds of ERF--k-ERF and k-APRF--which are useful in Exposure-Resilient cryptography.

Definition (k-ERF): An adaptive k-ERF is a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> where, for a random input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> , when a computationally unbounded adversary <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> can adaptively read all of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> except for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> bits, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}">

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}</annotation>

</semantics>

</math><img src="./48b9e279b6140f2fb1e5d6e0e58bed72f00eac65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.881ex; height:2.843ex;" alt="{\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}" loading="lazy"> for some negligible function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon (n)}</annotation>

</semantics>

</math><img src="./171c5965f691414e9d79ebbe5e6451bdb6a13468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.148ex; height:2.843ex;" alt="{\displaystyle \epsilon (n)}" loading="lazy"> (defined below).

The goal is to construct an adaptive ERF whose output is highly random and uniformly distributed. But a stronger condition is often needed in which every output occurs with almost uniform probability. For this purpose Almost-Perfect Resilient Functions (APRF) are used. The definition of an APRF is as follows:

Definition (k-APRF): A <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=k(n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=k(n)}</annotation>

</semantics>

</math><img src="./d466dcdff999795722ab2ae62f57bc2863bd5e3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.725ex; height:2.843ex;" alt="{\displaystyle k=k(n)}" loading="lazy"> APRF is a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> where, for any setting of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-k}</annotation>

</semantics>

</math><img src="./b98e1d6a69bccd09a4b9b69bdf03a08c1706c8c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.446ex; height:2.343ex;" alt="{\displaystyle n-k}" loading="lazy"> bits of the input <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> to any fixed values, the probability vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> of the output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(r)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(r)}</annotation>

</semantics>

</math><img src="./1498cdcc03367bb2fefb5da9fe91c89da0577540.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.137ex; height:2.843ex;" alt="{\displaystyle f(r)}" loading="lazy"> over the random choices for the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> remaining bits satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |p_{i}-2^{-m}|<2^{-m}\epsilon (n)}">

</mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |p_{i}-2^{-m}|<2^{-m}\epsilon (n)}</annotation>

</semantics>

</math><img src="./14cff55c644b1b8fe0e44e4122fc903b1ea7af0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.582ex; height:3.009ex;" alt="{\displaystyle |p_{i}-2^{-m}|<2^{-m}\epsilon (n)}" loading="lazy"> for all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> and for some negligible function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon (n)}</annotation>

</semantics>

</math><img src="./171c5965f691414e9d79ebbe5e6451bdb6a13468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.148ex; height:2.843ex;" alt="{\displaystyle \epsilon (n)}" loading="lazy">.

Kamp and Zuckerman<a href="#cite_note-David_Zuckerman_1242-6">[6]</a> have proved a theorem stating that if a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is a k-APRF, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is also a k-ERF. More specifically, any extractor having sufficiently small error and taking as input an oblivious, bit-fixing source is also an APRF and therefore also a k-ERF. A more specific extractor is expressed in this lemma:

Lemma: Any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-m}\epsilon (n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{-m}\epsilon (n)}</annotation>

</semantics>

</math><img src="./ee1d9135fbee266a9f0eb8f38a13963221cc5363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.264ex; height:3.009ex;" alt="{\displaystyle 2^{-m}\epsilon (n)}" loading="lazy">-extractor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}</annotation>

</semantics>

</math><img src="./7425a06fe8101145210179bbd52351f3cbe806b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.091ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}" loading="lazy"> for the set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)}</annotation>

</semantics>

</math><img src="./47f4659640cd0bb3ab77e4d61a81328ca4dd8a85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.449ex; height:2.843ex;" alt="{\displaystyle (n,k)}" loading="lazy"> oblivious bit-fixing sources, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon (n)}</annotation>

</semantics>

</math><img src="./171c5965f691414e9d79ebbe5e6451bdb6a13468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.148ex; height:2.843ex;" alt="{\displaystyle \epsilon (n)}" loading="lazy"> is negligible, is also a k-APRF.

This lemma is proved by Kamp and Zuckerman.<a href="#cite_note-David_Zuckerman_1242-6">[6]</a> The lemma is proved by examining the distance from uniform of the output, which in a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-m}\epsilon (n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{-m}\epsilon (n)}</annotation>

</semantics>

</math><img src="./ee1d9135fbee266a9f0eb8f38a13963221cc5363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.264ex; height:3.009ex;" alt="{\displaystyle 2^{-m}\epsilon (n)}" loading="lazy">-extractor obviously is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{-m}\epsilon (n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{-m}\epsilon (n)}</annotation>

</semantics>

</math><img src="./ee1d9135fbee266a9f0eb8f38a13963221cc5363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.264ex; height:3.009ex;" alt="{\displaystyle 2^{-m}\epsilon (n)}" loading="lazy">, which satisfies the condition of the APRF.

The lemma leads to the following theorem, stating that there in fact exists a k-APRF function as described:

Theorem (existence): For any positive constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma \leq {\frac {1}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma \leq {\frac {1}{2}}}</annotation>

</semantics>

</math><img src="./ee639efc90ccb751d1d444cf7f811ea42d97c5a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.359ex; height:5.176ex;" alt="{\displaystyle \gamma \leq {\frac {1}{2}}}" loading="lazy">, there exists an explicit k-APRF <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}</annotation>

</semantics>

</math><img src="./7425a06fe8101145210179bbd52351f3cbe806b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.091ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}" loading="lazy">, computable in a linear number of arithmetic operations on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">-bit strings, with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=\Omega (n^{2\gamma })}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=\Omega (n^{2\gamma })}</annotation>

</semantics>

</math><img src="./ddedf10f94a9b4b6337bd6d0484c5dc06f2da7a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.968ex; height:3.176ex;" alt="{\displaystyle m=\Omega (n^{2\gamma })}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=n^{{\frac {1}{2}}+\gamma }}">

<msup>

<mfrac>

</mfrac>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=n^{{\frac {1}{2}}+\gamma }}</annotation>

</semantics>

</math><img src="./8f5e81839483198b9faaacf7234e37f2b8c15e89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.611ex; height:3.509ex;" alt="{\displaystyle k=n^{{\frac {1}{2}}+\gamma }}" loading="lazy">.

Definition (negligible function): In the proof of this theorem, we need a definition of a <a href="Negligible_function" title="Negligible function">negligible function</a>. A function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon (n)}</annotation>

</semantics>

</math><img src="./171c5965f691414e9d79ebbe5e6451bdb6a13468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.148ex; height:2.843ex;" alt="{\displaystyle \epsilon (n)}" loading="lazy"> is defined as being negligible if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}">

<mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}</annotation>

</semantics>

</math><img src="./06a5d8ca148ac22354f98d200a3fa1201cd25d70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.003ex; height:6.176ex;" alt="{\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}" loading="lazy"> for all constants <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">.

Proof:

Consider the following <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy">-extractor: The function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is an extractor for the set of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (n,\delta n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,\delta n)}</annotation>

</semantics>

</math><img src="./4551844b0fcdda14095f126acf75eecb38766381.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.681ex; height:2.843ex;" alt="{\displaystyle (n,\delta n)}" loading="lazy"> oblivious bit-fixing source: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}</annotation>

</semantics>

</math><img src="./7425a06fe8101145210179bbd52351f3cbe806b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.091ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m=\Omega (\delta ^{2}n)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=\Omega (\delta ^{2}n)}</annotation>

</semantics>

</math><img src="./efb0d3947e1b7fe5e32d72b6f15053f15aeb2dbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.129ex; height:3.176ex;" alt="{\displaystyle m=\Omega (\delta ^{2}n)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon =2^{-cm}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon =2^{-cm}}</annotation>

</semantics>

</math><img src="./8d9f3a16a444d0017659151e4666587d62e5b36f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.871ex; height:2.509ex;" alt="{\displaystyle \epsilon =2^{-cm}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c>1}</annotation>

</semantics>

</math><img src="./bd1d6b5c226641ad3def8e65631f0eb463d9c67a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c>1}" loading="lazy">.

The proof of this extractor's existence with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta \leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta \leq 1}</annotation>

</semantics>

</math><img src="./5d42a08a5e8176ec7b7a22e9832b1361c8b50820.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.31ex; height:2.509ex;" alt="{\displaystyle \delta \leq 1}" loading="lazy">, as well as the fact that it is computable in linear computing time on the length of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> can be found in the paper by Jesse Kamp and David Zuckerman (p. 1240).

That this extractor fulfills the criteria of the lemma is trivially true as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon =2^{-cm}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon =2^{-cm}}</annotation>

</semantics>

</math><img src="./8d9f3a16a444d0017659151e4666587d62e5b36f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.871ex; height:2.509ex;" alt="{\displaystyle \epsilon =2^{-cm}}" loading="lazy"> is a negligible function.

The size of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=\Omega (\delta ^{2}n)=\Omega (n)\geq \Omega (n^{2\gamma })}</annotation>

</semantics>

</math><img src="./fb359b6d361ddb54323e68ad1d56e3a442536bb2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.037ex; height:3.176ex;" alt="{\displaystyle m=\Omega (\delta ^{2}n)=\Omega (n)\geq \Omega (n^{2\gamma })}" loading="lazy"></dd></dl>

Since we know <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta \leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta \leq 1}</annotation>

</semantics>

</math><img src="./5d42a08a5e8176ec7b7a22e9832b1361c8b50820.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.31ex; height:2.509ex;" alt="{\displaystyle \delta \leq 1}" loading="lazy"> then the lower bound on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is dominated by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. In the last step we use the fact that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma \leq {\frac {1}{2}}}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma \leq {\frac {1}{2}}}</annotation>

</semantics>

</math><img src="./ee639efc90ccb751d1d444cf7f811ea42d97c5a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:6.359ex; height:5.176ex;" alt="{\displaystyle \gamma \leq {\frac {1}{2}}}" loading="lazy"> which means that the power of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy">. And since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> is a positive integer we know that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n^{2\gamma }}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n^{2\gamma }}</annotation>

</semantics>

</math><img src="./6cd6b15f5b02e2e576ce868e1a3299cb9776ba69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.342ex; height:2.676ex;" alt="{\displaystyle n^{2\gamma }}" loading="lazy"> is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

The value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is calculated by using the definition of the extractor, where we know:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n,k)=(n,\delta n)\Rightarrow k=\delta n}</annotation>

</semantics>

</math><img src="./31512e8f3f8d35aa158f673e9dcab0f5724cd45d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.596ex; height:2.843ex;" alt="{\displaystyle (n,k)=(n,\delta n)\Rightarrow k=\delta n}" loading="lazy"></dd></dl>

and by using the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> we have:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m=\delta ^{2}n=n^{2\gamma }}</annotation>

</semantics>

</math><img src="./e9d7a860412492ed35110c045f5bd6d8ceb6f5f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.081ex; height:2.676ex;" alt="{\displaystyle m=\delta ^{2}n=n^{2\gamma }}" loading="lazy"></dd></dl>

Using this value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> we account for the worst case, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is on its lower bound. Now by algebraic calculations we get:

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta ^{2}n=n^{2\gamma }}</annotation>

</semantics>

</math><img src="./c8c32e0ca62b7ddcde23aede220ff36da644929f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.943ex; height:2.676ex;" alt="{\displaystyle \delta ^{2}n=n^{2\gamma }}" loading="lazy"></dd></dl>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Rightarrow \delta ^{2}=n^{2\gamma -1}}</annotation>

</semantics>

</math><img src="./69630eb99142df2fb2030079814630d487b39189.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.617ex; height:2.676ex;" alt="{\displaystyle \Rightarrow \delta ^{2}=n^{2\gamma -1}}" loading="lazy"></dd></dl>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Rightarrow \delta =n^{\gamma -{\frac {1}{2}}}}</annotation>

</semantics>

</math><img src="./b2ecc01d25a29de770759f4ef55850619eb9eeba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.418ex; height:3.509ex;" alt="{\displaystyle \Rightarrow \delta =n^{\gamma -{\frac {1}{2}}}}" loading="lazy"></dd></dl>

Which inserted in the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> gives

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=\delta n=n^{\gamma -{\frac {1}{2}}}n=n^{\gamma +{\frac {1}{2}}}}</annotation>

</semantics>

</math><img src="./5be2a77d9bb5ea597cd4271c45b61ebf6c3629f6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:24.948ex; height:3.509ex;" alt="{\displaystyle k=\delta n=n^{\gamma -{\frac {1}{2}}}n=n^{\gamma +{\frac {1}{2}}}}" loading="lazy">,</dd></dl>

which proves that there exists an explicit k-APRF extractor with the given properties. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Box }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Box }</annotation>

</semantics>

</math><img src="./029b77f09ebeaf7528fc831fe57848be51f2240b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Box }" loading="lazy">

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Von_Neumann_extractor">Von Neumann extractor</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Bernoulli_sequence" class="mw-redirect" title="Bernoulli sequence">Bernoulli sequence</a></div>

Perhaps the earliest example is due to <a href="John_von_Neumann" title="John von Neumann">John von Neumann</a>. From the input stream, his extractor took bits, two at a time (first and second, then third and fourth, and so on). If the two bits matched, no output was generated. If the bits differed, the value of the first bit was output. The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no <a href="Correlation" title="Correlation">correlation</a> between successive bits.<a href="#cite_note-7">[7]</a>

Thus, it takes as input a <a href="Bernoulli_sequence" class="mw-redirect" title="Bernoulli sequence">Bernoulli sequence</a> with p not necessarily equal to 1/2, and outputs a Bernoulli sequence with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p=1/2.}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p=1/2.}</annotation>

</semantics>

</math><img src="./795866b241d1c98c82cf208d6c67229ffa48f800.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:8.492ex; height:2.843ex;" alt="{\displaystyle p=1/2.}" loading="lazy">

More generally, it applies to any <a href="Exchangeable_random_variables" title="Exchangeable random variables">exchangeable sequence</a>—it only relies on the fact that for any pair, 01 and 10 are equally likely: for independent trials, these have probabilities <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\cdot (1-p)=(1-p)\cdot p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\cdot (1-p)=(1-p)\cdot p}</annotation>

</semantics>

</math><img src="./0a74e17c25a21ae6dfc7943bfea3d4cf10bf8155.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:22.848ex; height:2.843ex;" alt="{\displaystyle p\cdot (1-p)=(1-p)\cdot p}" loading="lazy">, while for an exchangeable sequence the probability may be more complicated, but both are equally likely. To put it simply, because the bits are <a href="Conditional_probability#Statistical_independence" title="Conditional probability">statistically independent</a> and due to the <a href="Commutative_property#Definition" title="Commutative property">commutative property</a> of multiplication, it would follow that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(A\cap B)=P(A)P(B)=P(B)P(A)=P(B\cap A)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(A\cap B)=P(A)P(B)=P(B)P(A)=P(B\cap A)}</annotation>

</semantics>

</math><img src="./c42847430d1ba155e187108885cf945ed1d0c0f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.817ex; height:2.843ex;" alt="{\displaystyle P(A\cap B)=P(A)P(B)=P(B)P(A)=P(B\cap A)}" loading="lazy">. Hence, if pairs of 01 and 10 are mapped onto bits 0 and 1 and pairs 00 and 11 are discarded, then the output will be a uniform distribution.

Iterations upon the Von Neumann extractor include the Elias and Peres extractor, the latter of which reuses bits in order to produce larger output streams than the Von Neumann extractor given the same size input stream.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading3"><h3 id="Chaos_machine">Chaos machine</h3></div>

Another approach is to use the output of a <a href="Chaos_machine" title="Chaos machine">chaos machine</a> applied to the input stream. This approach generally relies on properties of <a href="Chaotic_systems" class="mw-redirect" title="Chaotic systems">chaotic systems</a>. Input bits are pushed to the machine, evolving orbits and trajectories in multiple dynamical systems. Thus, small differences in the input produce very different outputs. Such a machine has a uniform output even if the distribution of input bits is not uniform or has serious flaws, and can therefore use weak <a href="Entropy_(computing)" title="Entropy (computing)">entropy sources</a>. Additionally, this scheme allows for increased complexity, quality, and security of the output stream, controlled by specifying three parameters: time cost, memory required, and secret key.

Note that while true chaotic systems are mathematically sound for 'amplifying' entropy, this is predicated on the availability of real numbers with an infinite precision. When implemented in digital computers with finite precision number representation, as in chaos machines using <a href="IEEE_754" title="IEEE 754">IEEE 754 Floating-Point</a>, the periodicity has been shown to fall far short of the full space for a given bit length. <a href="#cite_note-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Cryptographic_hash_function">Cryptographic hash function</h3></div>

It is also possible to use a <a href="Cryptographic_hash_function" title="Cryptographic hash function">cryptographic hash function</a> as a randomness extractor. However, not every hashing algorithm is suitable for this purpose.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

Randomness extractors are used widely in cryptographic applications, whereby a <a href="Cryptographic_hash" class="mw-redirect" title="Cryptographic hash">cryptographic hash</a> function is applied to a high-entropy, but non-uniform source, such as disk drive timing information or keyboard delays, to yield a uniformly random result.

Randomness extractors have played a major role in recent <a href="Quantum_cryptography" title="Quantum cryptography">quantum cryptography</a> developments, for example, distilling the raw output from a quantum random number generators into a shorter, secure and uniformly random output. <a href="#cite_note-10">[10]</a>

Randomness extraction is also used in some branches of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a> and in the construction of list-decodable <a href="Error_correcting_code" class="mw-redirect" title="Error correcting code">error correcting codes</a>.

<ul><li><a href="Decorrelation" title="Decorrelation">Decorrelation</a></li>

<li><a href="Hardware_random_number_generator" title="Hardware random number generator">Hardware random number generator</a></li>

<li><a href="Randomness_merger" title="Randomness merger">Randomness merger</a></li>

<li><a href="Fuzzy_extractor" title="Fuzzy extractor">Fuzzy extractor</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation book cs1"><a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=796582">Extracting randomness from sampleable distributions</a>. Portal.acm.org. 12 November 2000. p. 32. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780769508504</bdi>. Retrieved 2012-06-12.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> David K. Gifford, Natural Random Numbers, <a href="MIT" class="mw-redirect" title="MIT">MIT</a>/LCS/TM-371, Massachusetts Institute of Technology, August 1988.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFLuca_Trevisan" class="citation web cs1">Luca Trevisan. <a rel="nofollow" class="external text" href="http://theory.stanford.edu/~trevisan/pubs/extractor-full.pdf">"Extractors and Pseudorandom Generators"</a> (PDF). Retrieved 2013-10-21.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> Ronen Shaltiel. Recent developments in explicit construction of extractors. P. 5.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> Jesse Kamp and David Zuckerman. Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography., SIAM J. Comput., Vol. 36, No. 5, pp. 1231–1247.

</li>

<li id="cite_note-David_Zuckerman_1242-6">^ <a href="#cite_ref-David_Zuckerman_1242_6-0">a</a> <a href="#cite_ref-David_Zuckerman_1242_6-1">b</a> Jesse Kamp and David Zuckerman. Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. P. 1242.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> John von Neumann. Various techniques used in connection with random digits. Applied

Math Series, 12:36–38, 1951.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFPrasitsupparoteKonnoShikata2018" class="citation journal cs1">Prasitsupparote, Amonrat; Konno, Norio; Shikata, Junji (October 2018). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7512292">"Numerical and Non-Asymptotic Analysis of Elias's and Peres's Extractors with Finite Input Sequences"</a>. Entropy. 20 (10): 729. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2018Entrp..20..729P">2018Entrp..20..729P</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3390%2Fe20100729">10.3390/e20100729</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1099-4300">1099-4300</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7512292">7512292</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/33265818">33265818</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFPersohnPovinelli" class="citation web cs1">Persohn, Kyle; Povinelli, Richard. <a rel="nofollow" class="external text" href="https://epublications.marquette.edu/cgi/viewcontent.cgi?article=1103&context=electric_fac">"Analyzing Logistic Map Pseudorandom Number Generators for Periodicity Induced by Finite Precision Floating-Point Representation"</a>. Marquette University. Retrieved 3 January 2024.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFMaXuXuTan2013" class="citation journal cs1">Ma, Xiongfeng; Xu, Feihu; Xu, He; Tan, Xiaoqing; Qi, Bing; Lo, Hoi-Kwong (June 2013). "Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction". Physical Review A. 87 (6) 062327. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1207.1473">1207.1473</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013PhRvA..87f2327M">2013PhRvA..87f2327M</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevA.87.062327">10.1103/PhysRevA.87.062327</a>.</cite>

</li>

</ol></div></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.cs.washington.edu/homes/anuprao/pubs/thesis.pdf">Randomness Extractors for Independent Sources and Applications</a>, Anup Rao</li>

<li><a rel="nofollow" class="external text" href="http://www.cs.haifa.ac.il/~ronen/online_papers/survey.ps">Recent developments in explicit constructions of extractors</a>, Ronen Shaltiel</li>

<li><a rel="nofollow" class="external text" href="http://people.csail.mit.edu/dodis/ps/hmac.ps">Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes</a>, Yevgeniy Dodis et al.</li>

<li><a rel="nofollow" class="external text" href="http://eprint.iacr.org/2005/061.pdf">Key Derivation and Randomness Extraction</a>, Olivier Chevassut et al.</li>

<li><a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/users/diz/pubs/erf.pdf">Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography</a>, Jesse Kamp and David Zuckerman</li>

<li><a rel="nofollow" class="external text" href="http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf">Tossing a Biased Coin (and the optimality of advanced multi-level strategy) (lecture notes)</a>, Michael Mitzenmacher</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-21" href="https://en.wikipedia.org/wiki/?title=Randomness_extractor&oldid=1301704550">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>